package summary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/17 21:13
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 */
public class Title301 {

    static List<String> result;

    public static List<String> removeInvalidParentheses(String s) {
        int lremove = 0;
        int rremove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                lremove++;
            } else if (s.charAt(i) == ')') {
                if (lremove != 0) {
                    lremove--;
                }else{
                    rremove++;
                }
            }
        }
        result = new ArrayList<>();
        backTracking(s, lremove, rremove, 0);
        return result;
    }

    private static void backTracking(String s, int lremove, int rremove, int cur) {
        if (lremove == 0 && rremove == 0) {
            if (isValid(s)) {
                result.add(s);
            }
            return;
        }
        for (int i = cur; i < s.length(); i++) {
            //当i != cur时，进行去重判断
            if (i != cur && s.charAt(i) == s.charAt(i - 1)) {
                continue;
            }
            //剩余的字符不够最少删除的数量
            if (lremove + rremove > (s.length() - i)) {
                return;
            }
            //尝试去掉一个左括号
            if (lremove > 0 && s.charAt(i) == '(') {
                String newS = s.substring(0, i) + s.substring(i + 1);
                backTracking(newS,  lremove - 1, rremove,i);
            }
            if (rremove > 0 && s.charAt(i) == ')') {
                String newS = s.substring(0, i) + s.substring(i + 1);
                backTracking(newS, lremove, rremove - 1, i);
            }
        }
    }

    private static boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            } else if (c == ')') {
                if (count == 0) {
                    return false;
                }
                count--;
            }
        }
        return count == 0;
    }


    public static List<String> removeInvalidParentheses1(String s) {
        int lremove = 0;
        int rremove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                lremove++;
            } else if (s.charAt(i) == ')') {
                if (lremove != 0) {
                    lremove--;
                }else{
                    rremove++;
                }
            }
        }
        result = new ArrayList<>();
        backTracking(s, lremove, rremove, 0);
        return result;
    }

    public static void main(String[] args) {
        List<String> strings = removeInvalidParentheses("(())(");

        System.out.println();
    }
}
